
int
Insertion_sort_bin__get_index_binsearch(int what, int *array, int a_size)
	/*
	 * Modified for use in insertion sort
	 */
{
	int L = 0, R = a_size, M;
	while (L < R) {
		M = (L + R) / 2;
		if (what >= array[M])
			L = M+1;
		else
			R = M;
	}
	return L;
}



int
binsearch(int what, int *where, int size)
	/*
	 * Normal version
	 */
{
	int L = 0,
	    R = size - 1,
	    M;
	while (L < R) {
		M = (L+R)/2;
		if (what > where[M])
			L = M+1;
		else
			R = M;
	}
	return L;
}



void
halfInsertSort(int array[], int length)
	/*
	 * wikibooks.org. Nothing more to say
	 */
{
	int begin;
	int end;
	int middle;
	int value;
 
	for (int i = 1; i < length; ++i)
	{
		value = array[i];		   
		begin = 0;				  
		end = i - 1;				
		while (begin <= end)		
		{
			middle = (begin + end) / 2;   
			if (value < array[middle])
			{
				end = middle - 1;   
			}	  
			else						  
			{
				begin = middle + 1;	   
			}
		}
 
		for (int j = i - 1; j >= begin; --j) 
		{
			array[j + 1] = array[j];		 
		}
 
		array[begin] = value;				
	}
}
